package com.company.ljh.hard;

import java.util.*;

/**
 * @description:
 * 399. 除法求值
 * 提示
 * 中等
 * 956
 * 相关企业
 * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
 *
 * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
 *
 * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
 *
 * 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
 * @projectName:leet_code
 * @see:com.company.ljh.hard
 * @author:ljh
 * @createTime:2023/7/6 13:14
 * @version:1.0
 */
public class 除法求值 {
    public static void main(String[] args) {
        除法求值 test = new 除法求值();
        List<List<String>> equations = Arrays.asList(Arrays.asList(new String[]{"a", "b"}),Arrays.asList(new String[]{"b","c"}));
        List<List<String>> queries = Arrays.asList(Arrays.asList(new String[]{"a","c"}),Arrays.asList(new String[]{"b","a"}),Arrays.asList(new String[]{"x","x"}));
        double []values = new double[]{2.0,3.0};
        test.calcEquation(equations,values,queries);
    }
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //字符串字典，用于查找当前字符串的下标
        Map<String,Integer> dict = new HashMap();
        // //List字典，用于查找当前下标对应的字符串
        // List<String> indexDict = new ArrayList();

        int nodeSize = 0;
        //生成字符串字典
        for(int i =0 ;i < equations.size();i++){
            List<String> equation = equations.get(i);
            String firstStr = equation.get(0);
            String secondStr = equation.get(1);
            if(!dict.containsKey(firstStr)){
                dict.put(firstStr,nodeSize);
                nodeSize++;
            }
            if(!dict.containsKey(secondStr)){
                dict.put(secondStr,nodeSize);
                nodeSize++;
            }
        }

        //生成连接矩阵
        double [][]isConnected = new double[dict.size()][dict.size()];

        for(int i =0 ;i < equations.size();i++){
            double result = values[i];
            List<String> equation = equations.get(i);
            int firstStrIndex  = dict.get(equation.get(0));
            int secondStrIndex = dict.get(equation.get(1));
            isConnected[firstStrIndex][secondStrIndex] = result;
            isConnected[secondStrIndex][firstStrIndex] = 1/result;
        }
        //返回结果
        double[] result= new double[queries.size()];
        for(int i =0;i< result.length;i++){
            List<String> quest = queries.get(i);
            if(dict.containsKey(quest.get(0)) && dict.containsKey(quest.get(1))){
                int rootStrIndex = dict.get(quest.get(0));
                int findStrIndex = dict.get(quest.get(1));
                result[i] = dfs(isConnected,rootStrIndex,rootStrIndex,1,rootStrIndex,findStrIndex,new boolean[isConnected.length]);
            }else{
                result[i] = -1;
            }
        }

        return result;
    }
    //distince表示根节点到前节点的距离，root表示要找的根节点，
    public double dfs (double[][]isConnected,int preStrIndex,int thisStrIndex,double distince,int rootStrIndex,int findStrStrIndex,boolean isVisited[]){
        //距离更新,如果前驱节点是自己，则将自己到自己的距离更新为1
        distince = isConnected[preStrIndex][thisStrIndex] == 0?1:isConnected[preStrIndex][thisStrIndex] * distince;
        //刷新根节点到当前节点的距离
        isConnected[rootStrIndex][thisStrIndex] = distince;
        isConnected[thisStrIndex][rootStrIndex] = 1/distince;
        isVisited[thisStrIndex] =true;
        if(thisStrIndex == findStrStrIndex){
            //匹配到节点
            return distince;
        }else{
            //进行深度优先遍历
            for(int i =0;i<isConnected.length;i++){
                //访问下一个未访问节点
                if(!isVisited[i]&&isConnected[thisStrIndex][i] != 0){
                    double nextDistince = dfs(isConnected,thisStrIndex,i,distince,rootStrIndex,findStrStrIndex,isVisited);
                    if(nextDistince != -1){
                        return nextDistince;
                    }
                }
            }
            return -1;
        }

    }
}
